/*https://leetcode.cn/problems/numbers-with-repeated-digits/description/
1012.至少有1位重复的数字
medium, 方钊堉 2024.10.07
数位DP*/

class Solution {
public:
    int numDupDigitsAtMostN(int number) {
        string reversedNumber(to_string(number));
        reverse(reversedNumber.begin(), reversedNumber.end());
        int result = 0;
        
        // 计算位数少于 reversedNumber.size() 的所有无重复数字的数量
        for (int length = 1; length <= reversedNumber.size() - 1; length++) { 
            int totalOptions = 9, optionsLeft = 9;
            for (int i = 0; i < length - 1; i++) {
                totalOptions *= max(optionsLeft - i, 1);
            }
            result += totalOptions;
        }
        
        vector<bool> usedDigits(10, false);
        
        // 计算位数等于 reversedNumber.size() 且小于等于 number 的所有无重复数字的数量
        for (int position = reversedNumber.size() - 1; position >= 0; position--) {
            int validChoices = 0;
            for (int digit = 0; digit < reversedNumber[position] - '0'; digit++) {
                if (!usedDigits[digit]) validChoices++;
            }
            if (position == reversedNumber.size() - 1) validChoices--; // 排除前导零
            
            if (validChoices) {
                int remainingLength = position;
                int remainingOptions = 10 - (reversedNumber.size() - position);
                for (int i = 0; i < remainingLength; i++) {
                    validChoices *= max(remainingOptions - i, 1);
                }
                result += validChoices;
            }
            
            if (usedDigits[reversedNumber[position] - '0']) return number - result;
            usedDigits[reversedNumber[position] - '0'] = true;
        }
        
        return number - result - 1;
    }
};

